<div class="problemindexholder" problemindex="C">
 <div class="ttypography">
  <div class="problem-statement">
   <div class="header">
    <div class="title">
     C. Star sky
    </div>
    <div class="time-limit">
     <div class="property-title">
      time limit per test
     </div>
     2 seconds
    </div>
    <div class="memory-limit">
     <div class="property-title">
      memory limit per test
     </div>
     256 megabytes
    </div>
    <div class="input-file">
     <div class="property-title">
      input
     </div>
     standard input
    </div>
    <div class="output-file">
     <div class="property-title">
      output
     </div>
     standard output
    </div>
   </div>
   <div>
    <p>
     The Cartesian coordinate system is set in the sky. There you can see
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     stars, the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th has coordinates (
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     ), a maximum brightness
     <span class="tex-span">
      <i>
       c
      </i>
     </span>
     , equal for all stars, and an initial brightness
     <span class="tex-span">
      <i>
       s
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     (
     <span class="tex-span">
      0 ≤
      <i>
       s
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤
      <i>
       c
      </i>
     </span>
     ).
    </p>
    <p>
     Over time the stars twinkle. At moment
     <span class="tex-span">
      0
     </span>
     the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th star has brightness
     <span class="tex-span">
      <i>
       s
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     . Let at moment
     <span class="tex-span">
      <i>
       t
      </i>
     </span>
     some star has brightness
     <span class="tex-span">
      <i>
       x
      </i>
     </span>
     . Then at moment
     <span class="tex-span">
      (
      <i>
       t
      </i>
      + 1)
     </span>
     this star will have brightness
     <span class="tex-span">
      <i>
       x
      </i>
      + 1
     </span>
     , if
     <span class="tex-span">
      <i>
       x
      </i>
      + 1 ≤
      <i>
       c
      </i>
     </span>
     , and
     <span class="tex-span">
      0
     </span>
     , otherwise.
    </p>
    <p>
     You want to look at the sky
     <span class="tex-span">
      <i>
       q
      </i>
     </span>
     times. In the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th time you will look at the moment
     <span class="tex-span">
      <i>
       t
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
     </span>
     ) and the upper right — (
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
     </span>
     ). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.
    </p>
    <p>
     A star lies in a rectangle if it lies on its border or lies strictly inside it.
    </p>
   </div>
   <div class="input-specification">
    <div class="section-title">
     Input
    </div>
    <p>
     The first line contains three integers
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       q
      </i>
     </span>
     ,
     <span class="tex-span">
      <i>
       c
      </i>
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       n
      </i>
      ,
      <i>
       q
      </i>
      ≤ 10
      <sup class="upper-index">
       5
      </sup>
     </span>
     ,
     <span class="tex-span">
      1 ≤
      <i>
       c
      </i>
      ≤ 10
     </span>
     ) — the number of the stars, the number of the views and the maximum brightness of the stars.
    </p>
    <p>
     The next
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     lines contain the stars description. The
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th from these lines contains three integers
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       s
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       x
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ,
      <i>
       y
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤ 100
     </span>
     ,
     <span class="tex-span">
      0 ≤
      <i>
       s
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤
      <i>
       c
      </i>
      ≤ 10
     </span>
     ) — the coordinates of
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th star and its initial brightness.
    </p>
    <p>
     The next
     <span class="tex-span">
      <i>
       q
      </i>
     </span>
     lines contain the views description. The
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th from these lines contains five integers
     <span class="tex-span">
      <i>
       t
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       x
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
     </span>
     ,
     <span class="tex-span">
      <i>
       y
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
     </span>
     (
     <span class="tex-span">
      0 ≤
      <i>
       t
      </i>
      <sub class="lower-index">
       <i>
        i
       </i>
      </sub>
      ≤ 10
      <sup class="upper-index">
       9
      </sup>
     </span>
     ,
     <span class="tex-span">
      1 ≤
      <i>
       x
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
      &lt;
      <i>
       x
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
      ≤ 100
     </span>
     ,
     <span class="tex-span">
      1 ≤
      <i>
       y
      </i>
      <sub class="lower-index">
       1
       <i>
        i
       </i>
      </sub>
      &lt;
      <i>
       y
      </i>
      <sub class="lower-index">
       2
       <i>
        i
       </i>
      </sub>
      ≤ 100
     </span>
     ) — the moment of the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th view and the coordinates of the viewed rectangle.
    </p>
   </div>
   <div class="output-specification">
    <div class="section-title">
     Output
    </div>
    <p>
     For each view print the total brightness of the viewed stars.
    </p>
   </div>
   <div class="sample-tests">
    <div class="section-title">
     Examples
    </div>
    <div class="sample-test">
     <div class="input">
      <div class="title">
       Input
      </div>
      <pre>2 3 3<br/>1 1 1<br/>3 2 0<br/>2 1 1 2 2<br/>0 2 1 4 5<br/>5 1 1 5 5<br/></pre>
     </div>
     <div class="output">
      <div class="title">
       Output
      </div>
      <pre>3<br/>0<br/>3<br/></pre>
     </div>
     <div class="input">
      <div class="title">
       Input
      </div>
      <pre>3 4 5<br/>1 1 2<br/>2 3 0<br/>3 3 1<br/>0 1 1 100 100<br/>1 2 2 4 4<br/>2 2 1 4 7<br/>1 50 50 51 51<br/></pre>
     </div>
     <div class="output">
      <div class="title">
       Output
      </div>
      <pre>3<br/>3<br/>5<br/>0<br/></pre>
     </div>
    </div>
   </div>
   <div class="note">
    <div class="section-title">
     Note
    </div>
    <p>
     Let's consider the first example.
    </p>
    <p>
     At the first view, you can see only the first star. At moment
     <span class="tex-span">
      2
     </span>
     its brightness is
     <span class="tex-span">
      3
     </span>
     , so the answer is
     <span class="tex-span">
      3
     </span>
     .
    </p>
    <p>
     At the second view, you can see only the second star. At moment
     <span class="tex-span">
      0
     </span>
     its brightness is
     <span class="tex-span">
      0
     </span>
     , so the answer is
     <span class="tex-span">
      0
     </span>
     .
    </p>
    <p>
     At the third view, you can see both stars. At moment
     <span class="tex-span">
      5
     </span>
     brightness of the first is
     <span class="tex-span">
      2
     </span>
     , and brightness of the second is
     <span class="tex-span">
      1
     </span>
     , so the answer is
     <span class="tex-span">
      3
     </span>
     .
    </p>
   </div>
  </div>
  <p>
  </p>
 </div>
</div>
